package leetcode.回溯DFS;

import java.util.Arrays;

public class Leetcode879 {
    final int MAX = 1_000_000_007;
    int num;
    int[][][] dp;
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        this.num = group.length;
        this.dp = new int[group.length][n+1][minProfit+1];
        for (int i = 0; i < group.length; i++) {
            for(int j = 0;j<=n;j++){
                Arrays.fill(dp[i][j],-1);
            }
        }
        return dfs(n,minProfit,group,profit,minProfit,n,0);

    }

    public int dfs(int n, int minProfit, int[] group, int[] profit,int profits,int people,int index){
        if(index == num){
            if(profits==0){
                return 1;
            }else{
                return 0;
            }
        }
        if(dp[index][people][profits]!=-1){
            return dp[index][people][profits];
        }
        int ans = 0;
        ans = ans + dfs(n,minProfit,group,profit,profits,people,index+1);
        ans = ans % MAX;
        if(people-group[index]>=0){
            ans = ans + dfs(n,minProfit,group,profit,Math.max(profits-profit[index],0),people-group[index],index+1);
            ans = ans % MAX;
        }
        return dp[index][people][profits] = ans;
    }
}
